// 走迷宫问题
#include <stdio.h>

// 迷宫长宽
#define MAZE_SIZE 12

// 和栅格遍历问题思路差不多，可以用递归或者是栈实现，基本思想是深度优先遍历，只是结束条件有所变化
// 迷宫使用二维数组表示，0表示墙，1表示路，已经走过的路标记为2

/// @brief 深度优先递归遍历走迷宫
/// @param maze 表示迷宫的二维数组
/// @param startRow 迷宫入口/开始行数
/// @param startCol 迷宫入口/开始列数
/// @param outRow 迷宫出口行数
/// @param outCol 迷宫出口列数
/// @param count 找到路径个数，起始调用时传入为0的值的指针
void mazeDFS(int maze[][MAZE_SIZE], int startRow, int startCol, int outRow, int outCol, int *count)
{
	// 访问
	maze[startRow][startCol] = 2;
	// 若当前点为出口也结束递归并输出结果
	if (startRow == outRow && startCol == outCol)
	{
		// 指针值不能自加自减！
		*count = *count + 1;
		printf("第%d条路径（2为路径）：\n", *count);
		int i, j, length = 0;
		for (i = 0; i < MAZE_SIZE; i++)
		{
			for (j = 0; j < MAZE_SIZE; j++)
			{
				printf("%d ", maze[i][j]);
				if (maze[i][j] == 2)
				{
					length++;
				}
			}
			printf("\n");
		}
		printf("路径长度：%d\n", length);
		return;
	}
	// 四向递归
	int nextRow, nextCol;
	// 向上探索
	nextRow = startRow - 1;
	if (nextRow >= 0 && maze[nextRow][startCol] == 1)
	{
		mazeDFS(maze, nextRow, startCol, outRow, outCol, count);
		// 如果从这里出来了，说明上一步探索后遇到死路了，恢复回溯值
		// 下面几个是一样的
		maze[nextRow][startCol] = 1;
	}
	// 向下探索
	nextRow = startRow + 1;
	if (nextRow < MAZE_SIZE && maze[nextRow][startCol] == 1)
	{
		mazeDFS(maze, nextRow, startCol, outRow, outCol, count);
		maze[nextRow][startCol] = 1;
	}
	// 向左探索
	nextCol = startCol - 1;
	if (nextCol >= 0 && maze[startRow][nextCol] == 1)
	{
		mazeDFS(maze, startRow, nextCol, outRow, outCol, count);
		maze[startRow][nextCol] = 1;
	}
	// 向右探索
	nextCol = startCol + 1;
	if (nextCol < MAZE_SIZE && maze[startRow][nextCol] == 1)
	{
		mazeDFS(maze, startRow, nextCol, outRow, outCol, count);
		maze[startRow][nextCol] = 1;
	}
}

/// @brief 深度优先遍历走迷宫，使用栈非递归
/// @param maze 表示迷宫的二维数组
/// @param startRow 迷宫入口行数
/// @param startCol 迷宫入口列数
/// @param outRow 迷宫出口行数
/// @param outCol 迷宫出口列数
void mazeStack(int maze[][MAZE_SIZE], int startRow, int startCol, int outRow, int outCol)
{
	// 定义一个储存二维坐标的栈
	int top = 0;
	struct
	{
		int row, col; // 行列数
		int direct;	  // 表示该网格的下一步的方向，0-3分别表示上下左右，初始时为-1表示四个方向都没有尝试过
	} stack[144], *stackTop;
	// 之所以要记录方向，是因为在回溯恢复的时候，上一个格子应当从另一个方向尝试，否则会导致在两格间“原地踏步”
	// 分别表示找到的路径条数、路径长度、两个遍历下标、探索时下一个方格的行列数和是否探索到了下一条路
	int count = 0, length, i, j, nextRow, nextCol, findNext;
	// 起点先入栈并标记
	maze[startRow][startCol] = 2;
	stack[top].row = startRow;
	stack[top].col = startCol;
	stack[top].direct = -1;
	top++;
	while (top != 0)
	{
		// 取栈顶，栈顶表示当前所在的格子
		stackTop = &stack[top - 1];
		// 如果此时已走到终点，则输出结果
		if (stackTop->row == outRow && stackTop->col == outCol)
		{
			length = 0;
			count++;
			printf("第%d条路径（2为路径）：\n", count);
			for (i = 0; i < MAZE_SIZE; i++)
			{
				for (j = 0; j < MAZE_SIZE; j++)
				{
					printf("%d ", maze[i][j]);
					if (maze[i][j] == 2)
					{
						length++;
					}
				}
				printf("\n");
			}
			printf("路径长度：%d\n", length);
		}
		// 四向探索
		findNext = 0;
		while (stackTop->direct < 4)
		{
			// 从当前方格的下一个方向进行探索（不再走上次尝试过的方向）
			stackTop->direct++;
			switch (stackTop->direct)
			{
			case 0:
				nextRow = stackTop->row - 1;
				nextCol = stackTop->col;
				break;
			case 1:
				nextRow = stackTop->row + 1;
				nextCol = stackTop->col;
				break;
			case 2:
				nextRow = stackTop->row;
				nextCol = stackTop->col - 1;
				break;
			case 3:
				nextRow = stackTop->row;
				nextCol = stackTop->col + 1;
				break;
			}
			// 每换一次方向就看一下是否可走，可以走则跳出循环
			if (nextRow >= 0 && nextRow < MAZE_SIZE && nextCol >= 0 && nextCol < MAZE_SIZE && maze[nextRow][nextCol] == 1)
			{
				// 往下走一步
				maze[nextRow][nextCol] = 2;
				// 下一个格子标记并进栈
				stack[top].row = nextRow;
				stack[top].col = nextCol;
				// 由于下一个格子未尝试任何方向，因此方向为-1
				stack[top].direct = -1;
				top++;
				findNext = 1;
				break;
			}
		}
		// 到这里说明无路可走了，退栈，并将退栈的方格恢复为1
		if (!findNext)
		{
			maze[stackTop->row][stackTop->col] = 1;
			top--;
		}
	}
}

int main()
{
	// 初始化数据
	int maze[MAZE_SIZE][MAZE_SIZE] = {
		{1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0},
		{1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0},
		{0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0},
		{0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0},
		{0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0},
		{0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0},
		{0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1},
		{0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1},
		{0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
		{0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1},
		{0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1},
		{0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1}};
	int count = 0;
	mazeDFS(maze, 0, 0, 11, 11, &count);
	// mazeStack(maze, 0, 0, 11, 11);
	return 0;
}